﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._30
{
    public class Leetcode29
    {
        /*
         29. Divide Two Integers

         Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT. 
         */

         /// <summary>
         /// 通过网上的移位启发。。自己摸索着写的。。效率比不上别人。。
         /// </summary>
         /// <param name="dividend"></param>
         /// <param name="divisor"></param>
         /// <returns></returns>
        public int Divide(int dividend, int divisor)
        {
            if (dividend == int.MinValue && divisor == -1)
                return int.MaxValue;
            if (divisor == 1)
                return dividend;
            if (divisor == 0)
                return int.MaxValue;
            bool isNegative = false;
            if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0)
                isNegative = true;


            long lDividend = Math.Abs((long)dividend);
            long lDivisor = Math.Abs((long)divisor);
            if (lDividend < lDivisor || lDividend == 0)
                return 0;
            long iResult = 0;
            long tempDivisor = lDivisor;
            while(tempDivisor <= lDividend)
            {
                tempDivisor = tempDivisor << 1;
                if (iResult == 0)
                    iResult = 2;
                else
                    iResult = iResult << 1;
            }

            if (iResult == 2)
                iResult -= 1;
            else
            {
                if (tempDivisor - lDividend < lDividend - (tempDivisor >> 1))
                {
                    while (tempDivisor >= lDividend)
                    {
                        tempDivisor -= lDivisor;
                        iResult--;
                    }
                }
                else
                {
                    iResult = iResult >> 1;
                    tempDivisor = tempDivisor >> 1;
                    tempDivisor = tempDivisor + lDivisor;
                    while (tempDivisor <= lDividend)
                    {
                        tempDivisor = tempDivisor + lDivisor;
                        iResult++;
                    }
                }
                
            }
            if (isNegative)
                return -(int)iResult;
            return (int)iResult;
        }
    }
}
